package summary;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/18 9:59
 * https://leetcode-cn.com/problems/pacific-atlantic-water-flow/
 */
public class Title417 {

    static int n;
    static int m;

    public static List<List<Integer>> pacificAtlantic(int[][] heights) {
        n = heights.length;
        m = heights[0].length;
        List<List<Integer>> result = new ArrayList<>();
        boolean[][] canReachP = new boolean[n][m];
        boolean[][] canReachA = new boolean[n][m];
        //行
        for (int i = 0; i < n; i++) {
            dfs(heights, canReachP, i, 0,0);
            dfs(heights, canReachA, i, m - 1,0);
        }
        //列
        for (int j = 0; j < m; j++) {
            dfs(heights, canReachP, 0, j,0);
            dfs(heights, canReachA, n - 1, j, 0);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (canReachP[i][j] && canReachA[i][j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    result.add(temp);
                }
            }
        }
        return result;
    }

    /**
     * 水往高处流
     * @param heights
     * @param canReach
     * @param i
     * @param j
     */
    private static void dfs(int[][] heights, boolean[][] canReach, int i, int j, int preValue) {
        if (i < 0 || i >= n || j < 0 || j >= m || canReach[i][j] || preValue > heights[i][j]) {
            return;
        }
        canReach[i][j] = true;
        //上下左右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        for (int k = 0; k < 4; k++) {
            dfs(heights, canReach, i + dx[k], j + dy[k], heights[i][j]);
        }
    }


    public static void main(String[] args) {
        int[][] arr = {{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
        pacificAtlantic(arr);
    }
}
